package 树;

public class Leedcode105从前序与中序遍历序列构造二叉树 {
    /**
     * 传入先序遍历和中序遍历的结果，就可以根据结果还原一个二叉树
     * @param preorder
     * @param inorder
     * @return
     */
    private  int index = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder,inorder,0,preorder.length - 1);
    }

    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int left, int right) {
        //终止条件
        if (left > right){
            return null;
        }
        if (index > preorder.length){
            return null;
        }
        //将前序遍历的节点作为根节点
        TreeNode root = new TreeNode(preorder[index]);
        index++;
        //find：在中序遍历的结果中找到当前节点的位置
        int pos = find(inorder, (Integer) root.val);
        //中序遍历的左子树在节点的左边，因此在左边寻找左子树
        root.left = buildTreeHelper(preorder,inorder,0,pos-1);
        //在右边寻找右子树
        root.right = buildTreeHelper(preorder,inorder,pos+1,right);
        //最终循环结束，返回根节点
        return root;
    }

    private int find(int[] inorder, int val) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == val){
                return i;
            }
        }
        return -1;
    }


}
